package mo.leetcode_top;

import mo.common.TreeNode;

import java.util.LinkedList;

public class L297 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder builder = new StringBuilder();

        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.addLast(root);
        while (!nodes.isEmpty()) {
            TreeNode treeNode = nodes.removeFirst();
            if (treeNode != null) {
                nodes.addLast(treeNode.left);
                nodes.addLast(treeNode.right);
                builder.append(treeNode.val);
            } else {
                builder.append("null");

            }
            builder.append(",");
        }

        String[] split = builder.deleteCharAt(builder.length()-1).toString().split(",");
        for (int i = split.length - 1; i >= 0; i--) {
            if ("null".equals(split[i])) {
                split[i] = "";
            } else {
                break;
            }
        }
        StringBuilder res = new StringBuilder("[");
        for (int i = 0; i < split.length; i++) {
            if (split[i].length() > 0) {
                res.append(split[i]).append(',');
            } else {
                break;
            }
        }
        res.setCharAt(res.length()-1, ']');
        return  res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String real = data.substring(1, data.length() - 1);
        if (real.length() == 0) {
            return null;
        }
        String[] nodeData = real.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodeData[0]));
        int i = 1;
        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.addLast(root);
        while (!nodes.isEmpty() && i < nodeData.length) {
            TreeNode node = nodes.removeFirst();
            String leftData = nodeData[i];
            if (!"null".equals(leftData)) {
                node.left = new TreeNode(Integer.parseInt(leftData));
                nodes.addLast(node.left);
            }
            i++;
            if (i == nodeData.length) {
                break;
            }
            String rightData = nodeData[i];
            if (!"null".equals(rightData)) {
                node.right = new TreeNode(Integer.parseInt(rightData));
                nodes.addLast(node.right);
            }
            i++;
            if (i == nodeData.length) {
                break;
            }
        }
        return root;
    }


    public static void main(String[] args) {
        L297 test = new L297();
        TreeNode treeNode = test.deserialize("[1,2,3,null,null,4,5]");
        String serialize = test.serialize(treeNode);
        System.out.println(serialize);
    }

}
